Mo's Algorithm

概要

平方分割で区間に対するクエリを高速にやるやつ

条件は

配列が変わらない

オフラインクエリ

区間$ [l,r) についての結果がわかってるとき、区間長を$ \pm 1した結果が簡単に求まる

で、計算量$ O(\alpha N\sqrt{Q})

手順

クエリ$ [l,r) を$ l の値$ \lfloor l \times \sqrt{Q} / N \rfloor 毎の$ \sqrt{Q} 個にグループ分け

各グループのクエリを$ r の昇順に並び替え

順番に処理していく

$ l, rを伸ばしたり縮めたりして合わせる→値を記録　の繰り返し

計算量

$ l の移動は最大$ N / \sqrt{Q} が$ Q 回で全体$ O(N\sqrt{Q})回

$ r の移動はざっくり$ N が$ \sqrt{Q} 回で全体$ O(N\sqrt{Q})回

1回の移動に$ O( \alpha )

∴ 全部で$ O(\alpha N \sqrt{Q})

高速化

$ r の昇順・降順を交互にすることで、$ r の移動がざっくり$ N が$ \sqrt{Q} / 2 回になって定数倍良くなる

$ l の幅は$ {\sqrt{3}N} / {\sqrt{2Q}} がベストらしい

全体をヒルベルト曲線の順番で並び替える方法もあるらしい

問題例

PythonだとN = 2*10^5でO(α)=軽めのO(1)くらいなら間に合う

間に合ったやつ

間に合ってないやつ

参考